package com.example.algorithm.no0440.solution;

import com.example.algorithm.no0440.Solution;

/**
 * @Description 解答-字典序的第K小数字
 * @ClassName SolutionImpl
 * @Author Administrator
 * @Date 2020/5/20 10:26
 * @Version 1.0.0
 */
public class SolutionImpl1 implements Solution {

    // n=13, k=2
    @Override
    public int findKthNumber(int n, int k) {
        int prefix = 1;
        int count = 1;
        while(count < k) {
            int curCount = count(n, prefix);
            if(curCount + count > k) {
                prefix *= 10;
                count++;
            } else {
                prefix++;
                count += curCount;
            }
        }
        return prefix;
    }

    // n=13, prefix=1
    private int count(int n, long prefix) {
        long nextPrefix = prefix + 1;
        int count = 0;
        while(prefix <= n) {
            count += Math.min(n + 1, nextPrefix) - prefix;
            prefix *= 10;
            nextPrefix *= 10;
        }
        return count;
    }
}
